class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def flipMatchVoyage(self, root, voyage):
        """
        :type root: TreeNode
        :type voyage: List[int]
        :rtype: List[int]
        """
        out = []

        def search(node, i, j):
            if node.val != voyage[i]:
                return False
            if i > j:
                return False
            left_index = -1
            right_index = -1
            if node.left:
                for index in range(i + 1, j + 1):
                    if voyage[index] == node.left.val:
                        left_index = index
                        break
                if left_index == -1:
                    return False
            if node.right:
                for index in range(i + 1, j + 1):
                    if voyage[index] == node.right.val:
                        right_index = index
                        break
                if right_index == -1:
                    return False
            if left_index == -1:
                if right_index == -1:
                    return True
                else:
                    return search(node.right, right_index, j)
            else:
                if right_index == -1:
                    return search(node.left, left_index, j)
                else:
                    if left_index < right_index:
                        return search(node.left, left_index, right_index - 1) and search(node.right, right_index, j)
                    else:
                        out.append(node.val)
                        return search(node.left, left_index, j) and search(node.right, right_index, left_index - 1)
        if search(root,0, len(voyage) - 1):
            return out
        else:
            return [-1]



